/***尚硅谷Java数据结构与java算法                 ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***二叉排序树                                  ***/
/***C++ 实现版本    written by Daniel           ***/
#include <string>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;

class Node
{
public:
	//构造函数
	Node() = delete;
	Node(int value) : value(value), left(nullptr), right(nullptr) {}
	Node(int value, Node *left, Node *right) : value(value), left(left), right(right) {}
	Node(Node &) = delete;
	Node(Node &&) = delete;
	/*
	功能：向排序二叉树中添加一个节点
	参数：node，需要被添加的节点
	返回值：void空
	*/
	void addNode(Node *node)
	{
		//向左边放置
		if (node->value < this->value)
		{
			if (this->left == nullptr)
			{
				this->left = node;
			}
			else
			{
				this->left->addNode(node);
			}
		}
		else
		{
			if (this->right == nullptr)
			{
				this->right = node;
			}
			else
			{
				this->right->addNode(node);
			}
		}
		//每次增加节点的时候需要判断是否需要进行平衡操作
		if (left->getHeight() - right->getHeight() > 1)
		{
			//进行右旋  右旋之前判断左节点  右子树的高度是否大于左子树的高度
			if (left != nullptr && left->right->getHeight() > left->left->getHeight() )
			{
				left->leftRotate();
			}
			this->rightRotate();
			return;
		}
		if (right->getHeight() - left->getHeight() > 1)
		{
			//进行左旋  左旋之前判断右子节点  左子树的高度是否大于右子树的高度
			if (right != nullptr && right->left->getHeight()>right->right->getHeight() )
			{
				right->rightRotate();
			}
			this->leftRotate();
		}
		return;
	}
	//中序遍历函数
	void infixOrder()
	{
		if (this->left != nullptr)
		{
			this->left->infixOrder();
		}
		cout << this->transToStr() << endl;
		if (this->right != nullptr)
		{
			this->right->infixOrder();
		}
	}
	//打印函数
	string transToStr()
	{
		string resStr("value=" + std::to_string(this->value));
		return resStr;
	}
	/*
	功能：给定一个value，返回该节点的指针
	参数：value  需要查找的值
	返回值：value==value  节点的指针，不存在，返回空指针
	*/
	Node *search(int value)
	{
		if (this->value == value)
		{
			return this;
		}
		else if (value < this->value)
		{
			//左子节点不为空的情况下，向左子树查找
			if (this->left != nullptr)
			{
				this->left->search(value);
			}
			else
			{
				return nullptr;
			}
		}
		else
		{
			if (this->right != nullptr)
			{
				this->right->search(value);
			}
			else
			{
				return nullptr;
			}
		}
	}
	/*
	功能：给定一个value，返回节点的value等于该value的父节点
	参数：value  需要查找的值
	返回值：返回 父节点，如果没有，返回空；
	*/
	Node *searchParent(int value)
	{
		//找到了父节点
		if (((this->left != nullptr) && (this->left->value == value)) ||
			((this->right != nullptr) && (this->right->value == value)))
		{
			return this;
		}
		/*向左查找*/
		if ((this->left != nullptr) && (value < this->value))
		{
			this->left->searchParent(value);
		}
		/*向右查找*/
		else if ((this->right != nullptr) && (value >= this->value))
		{
			this->right->searchParent(value);
		}
	}
	/*
	功能：实现平衡二叉树的左旋
	参数：空
	返回值： void 空
	*/
	void leftRotate()
	{
		//创建一个新的节点，使用现在节点的值进行初始化
		Node *newNode = new Node(this->value);
		//将当前节点的左子树，设置为新节点的左子树
		newNode->left = this->left;
		//将当前节点的右子树的左子树  设置为  新节点的右子树
		//因为我们想把右子节点作为根节点，  而右子节点的左子树的所有值都大于根节点
		//而比新的根节点小，所以适合放在左子节点的右子树
		newNode->right = this->right->left;
		//把当前节点的值更换为右子节点的值
		this->value = this->right->value;
		this->left = newNode;
		auto nodeToDel = this->right;
		auto tempNode = this->right->right;
		this->right = tempNode;
		if (nodeToDel != nullptr)
		{
			nodeToDel->left = nullptr;
			nodeToDel->right = nullptr;
			delete nodeToDel;
			nodeToDel = nullptr;
		}
	}
	/*
	功能：实现平衡二叉树的右旋
	参数：空
	返回值： void 空
	*/
	void rightRotate()
	{
		//创建新的节点
		Node *newNode = new Node(this->value);
		//新节点的右子树还是原来的右子树
		newNode->right = this->right;
		//新节点的左子树是  左子节点的右子树
		newNode->left = this->left->right;
		this->value = this->left->value;
		this->right = newNode;
		auto nodeToDel = this->left;
		this->left = this->left->left;
		if (nodeToDel != nullptr)
		{
			nodeToDel->left = nullptr;
			nodeToDel->right = nullptr;
			delete nodeToDel;
			nodeToDel = nullptr;
		}
	}

	bool operator==(Node &node)
	{
		if ((this->value == node.value) && (this->left == node.left) && (this->right == node.right))
		{
			return true;
		}
		else
			return false;
	}
	/*
	功能：查找以该节点为根节点的子树的最大值
	参数： root 该节点的指针
	返回值：找到的最大值
	*/
	int findMax()
	{
		if (this->right != nullptr)
		{
			return this->right->findMax();
		}
		else
			return this->value;
	}
	/*
	功能：查找以该节点为根节点的子树的最小值
	参数： root 该节点的指针
	返回值：找到的最大值
	*/
	int findMin()
	{
		if (this->left != nullptr)
		{
			return this->left->findMin();
		}
		else
			return this->value;
	}

	//析构函数
	~Node()
	{
		if (this->left == nullptr && this->right == nullptr)
		{
			return;
		}
		if (this->left != nullptr)
		{
			delete this->left;
			this->left = nullptr;
		}
		if (this->right != nullptr)
		{
			delete this->right;
			this->right = nullptr;
		}
	}
	int getHeight()
	{
		int leftHeight = 0, rightHeight = 0;
		if (this==nullptr){
			return 0;
		}
		if ((this->left == nullptr) && (this->right == nullptr))
		{
			return 1;
		}
		if (this->left != nullptr)
		{
			leftHeight = this->left->getHeight() + 1;
		}
		if (this->right != nullptr)
		{
			rightHeight = this->right->getHeight() + 1;
		}
		return leftHeight > rightHeight ? leftHeight : rightHeight;
	}
	int value;
	Node *left;
	Node *right;
};

//二叉排序树
class AVLTree
{
public:
	AVLTree() : root(nullptr){};
	AVLTree(Node *root) : root(root) {}
	AVLTree(AVLTree &) = delete;
	AVLTree(AVLTree &&) = delete;
	Node *getRoot()
	{
		return root;
	}
	int getHeight()
	{
		if (root == nullptr)
		{
			return 0;
		}
		return root->getHeight();
	}
	void addNode(Node *node)
	{
		if (this->root == nullptr)
		{
			this->root = node;
		}
		else
		{
			root->addNode(node);
		}
	}

	void infixOrder()
	{
		if (this->root == nullptr)
		{
			cout << "二叉树为空，无法中序遍历" << endl;
		}
		else
		{
			root->infixOrder();
		}
	}
	Node *search(int value)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		return root->search(value);
	}
	Node *searchParent(int value)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		return root->searchParent(value);
	}

	/*
	功能：删除节点
	参数：value  待删除节点的值
	返回值：void
	*/
	void delNode(int value)
	{
		//先查找有无要删除的值
		auto toDelNode = search(value);
		//没查到该值，直接返回
		if (toDelNode == nullptr)
		{
			return;
		}
		//查到树中有节点值等于该值的节点
		//讨论：叶子节点？含有一个子树？含有两个子树？
		else
		{ //叶子节点的删除
			cout << "toDelNode=" << toDelNode->transToStr() << endl;
			if ((toDelNode->left == nullptr) && (toDelNode->right == nullptr))
			{ //如果要删除的是根节点
				if (root == toDelNode)
				{
					delete root;
					root = nullptr;
					return;
				} //如果不是根节点，找到父节点之后，删除
				else
				{
					auto parentNode = searchParent(value);
					cout << "parentNode=" << parentNode->transToStr() << endl;
					if ((parentNode->left != nullptr) && (parentNode->left->value == value))
					{
						delete parentNode->left;
						parentNode->left = nullptr;
						return;
					}
					else
					{
						delete parentNode->right;
						parentNode->right = nullptr;
						return;
					}
				}
			}
			//有两颗子树的情况
			else if ((toDelNode->left != nullptr) && (toDelNode->right != nullptr))
			{
				//找出左子树的最大值，或者右子树的最小值，用这个值替换找到的节点，并且删掉这个值的节点
				int tempVal = toDelNode->left->findMax();
				this->delNode(tempVal);
				toDelNode->value = tempVal;
				return;
			}
			//只有一颗子树的情况   左子树为空，或者右子树为空
			else
			{ //并且要删除的节点是根节点，那么不需要考虑父节点的情况
				if (toDelNode == root)
				{
					//向root指向指针不为空的树
					root = (toDelNode->left == nullptr ? toDelNode->right : toDelNode->left);
					//删除toDelNote节点，删除之前，要将其左右节点置为nullptr，否则会删除整棵树
				}
				//如果待删除的节点不是根节点
				else
				{
					//找到其父节点
					auto parentNode = root->searchParent(value);
					if (parentNode != nullptr)
					{
						cout << "my parent is： " << parentNode->transToStr() << endl;
					}
					if ((parentNode->left != nullptr) && (parentNode->left->value == value))
					{
						parentNode->left = (toDelNode->left == nullptr ? toDelNode->right : toDelNode->left);
					}
					else
					{
						parentNode->right = (toDelNode->left == nullptr ? toDelNode->right : toDelNode->left);
					}
				}
				if (toDelNode != nullptr)
				{
					toDelNode->left = nullptr;
					toDelNode->right = nullptr;
					delete toDelNode;
					toDelNode = nullptr;
				}
				return;
			}
		}
	}
	void leftRotate()
	{
		root->leftRotate();
	}
	void rightRotate()
	{
		root->rightRotate();
	}
	~AVLTree()
	{
		if (root != nullptr)
		{
			delete root;
			root = nullptr;
		}
	}

private:
	Node *root;
};

int main()
{
	vector<int> intVec({10,11,7,6,8,9});
	auto len = intVec.size();
	AVLTree avlTree;
	for (size_t i = 0; i < len; i++)
	{
		Node *node = new Node(intVec[i]);
		avlTree.addNode(node);
	}
	avlTree.infixOrder();
	cout<<avlTree.getRoot()->left->getHeight()<<endl;
	cout<<avlTree.getRoot()->right->getHeight()<<endl;
	return 0;
}